1. Field of the Invention
The present invention relates to a task management system suitable for, for example, an operating system (OS).
2. Description of the Related Art
It has conventionally been one of the important aims of a real-time OS to enhance the effective use of a processor's time capable of being occupied by task execution, while guaranteeing that the upper limit of a task's response time is equal to or less than a predetermined value set as a deadline. To achieve this aim, it is possible to use the following scheduling techniques.
First, it is possible to employ superior dispatch policies.
The Earliest Deadline First (EDF) policy (reference: C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard real time environment”, Journal of ACM, Vol. 20, No. 1, pp. 46-61, 1973) is known as one dispatch policy. The EDF policy is known as one that can achieve the highest processor-use factor in techniques that perform scheduling of periodic tasks each having a period equal to that of a deadline. However, preconditions are essential, such as no interference between tasks, and the use of a single processor.
Second, it is possible to minimize the time for which a higher priority task is blocked by a lower priority task. By employing a priority inheritance protocol (reference: Lui, Sha, Raguntathan Rajkumar, and John P. Lehoczky, “Priority Inheritance Protocols: An Approach to Real-time Synchronization”, IEEE Transactions on Computers, Vol. 39, No. 9, pp. 1175-1185, September 1990), the time for which the higher priority task is blocked can be reduced by using the lower priority task. Here, priority inheritance protocol is used as a generic term for a basic priority inheritance protocol and a priority ceiling protocol.
In addition, in order to realize stable system operation, in system construction, by dividing the system into a plurality of modules and executing the modules in different address spaces, one module is prevented from mistakenly destroying data of another module.
Also, in general, individual tasks cannot pass the boundary of each module. In this system, in order that one module may use a function of another module, a mechanism for calling a procedure in a different address space is provided in most situations.
In this case, whenever use of a service is attempted, processing for stopping or starting a client task and a server task must be performed. The time required for stopping or starting frequently occupies a not insignificant amount of time with respect to the total of the service time, although it depends on the time required for providing the service. This problem may be worse in a scheduler employing the EDF policy because its overhead tends to increase compared with schedulers of the related art.
Moreover, an increase in the overhead associated with a priority change of the server task must also be taken into consideration. In general, client tasks have various types of urgency. Thus, it is preferable that the server task process a request with a priority identical to client task priority.
Accordingly, when requesting a service, the server task priority is frequently changed, depending on the client task priority. An overhead generated due to this priority change or termination is added to the overhead caused by starting or stopping the server task and the client task.
The above-described scheduling technique of the related art has the following problems.
First, an EDF scheduler employing the EDF policy has an overhead larger than that in a static priority scheduler using fixed priority, which is widely used in known OSs.
Second, a scheduler employing the priority inheritance protocol has a large overhead, which indicates that execution time is that of a general case. In particular, when this scheduler is used in combination with the above EDF scheduler, the overhead is larger than that in the case of using the static priority scheduler.
These points are further described below.
One of the causes of the larger overhead in the EDF scheduler compared with the static priority scheduler is that the range of priorities that the EDF scheduler must handle is large, and as a result, it is difficult to efficiently implement a dispatch queue.
Since, in general, processing that adds a task to the dispatch queue or processing that deletes a task from the dispatch queue is executed very frequently, it is preferable that this processing be executed as efficiently as possible. Although processing that selects a highest priority task from the dispatch queue is not so frequently executed compared with the adding or removing processing, its frequency is higher.
In order to efficiently realize these two operations, a system that performs static priority scheduling, in many cases, implements the dispatch queue by using the data configuration shown in FIG. 9. In this implementation, one element of the elements 1 to n of an array is assigned to each priority 91. This element is used as the start point of a bidirectional link list of tasks having the same priority. In the bit stream 92 at the bottom left of FIG. 9, the 1's indicates that tasks 93 to 95 are linked to the bidirectional link list and that tasks 96 and 97 are also linked to the bidirectional link list.
In this data configuration, the task adding processing and the task deleting processing can be executed in a constant time that is short in practice. Also, the processing that selects the highest priority task can be executed by calculating the position in which the first “1” appears in the bit stream 92. This is a case in which, when there is a task linked to the bidirectional link list, “1” is stored in the bit stream 92. When “1” is stored, the first “0” must be found. When the static priority scheduler is used, 256, or slightly less is common as a possible range of priorities. Accordingly, the time required for the calculation does not become a problem in practical use. An array for the start point of the bidirectional link list and the size of the bit stream are also sufficiently small.
On the contrary, when the EDF scheduling is used, the whole possible range of times must be used. Here, a technique that correlates a time with a value having a smaller possible range has also been proposed. This, however, has a possibility that processing for sorting the priorities of many tasks may occur in the operating time of the system. Accordingly, a technique that performs efficient processing on a wider range of priorities is required.
Regarding this type of technique, a linear list, a heap, a splay tree, a calendar queue (reference: Randy Brown, “Calendar Queues: A Fast (1) Priority Queue Implementation for the Simulation Event Set Problem”, Volume 31, November 10, Communications of the ACM, October 1988), etc., are known.
The performance achievable by the data configurations of the above techniques is lower than that achievable by the data configuration shown in FIG. 9. Accordingly, it is difficult for a system employing EDF scheduling to reduce the cost required for the dispatch queue operation.
One of the reasons why mutual exclusion (mutex) for preventing two tasks employing the priority inheritance protocol from simultaneously being executed has an overhead larger than that of ordinary mutex is that the priority changes due to priority inheritance. In general, when the priority of a task changes, some operation must be performed for the dispatch queue. This particularly becomes a problem in the case of the EDF scheduler, in which the cost required for the operation is large.
In addition to the above-described factor, the overhead of the priority inheritance protocol includes overhead generated by performing queuing in which tasks having mutex are controlled to queue in the order of priority. Also, when employing the priority ceiling protocol that stores information on which mutex is locked, whenever the mutex lock operation is performed, mutexes that are locked by other tasks must be searched in order to find one in which the maximum ceiling value is set.
Although the EDF scheduling and the priority inheritance protocol have superior characteristics, they tend to have a larger overhead than in cases where they are not employed.
Third, when the server task priority is changed for a service request in accordance with the client task priority, the overhead generated due to the priority change or termination is added to the overhead generated by starting or stopping the server task and the client task. Thus, the overhead increases even more.